iT邦幫忙

2024 iThome 鐵人賽

DAY 13
0

題目

1310. XOR Queries of a Subarray
難度: 中等偏易

題意

給定一整數陣列arr;給定一整數陣列的陣列queries,其中queries[i]為[left, right]陣列,代表一個區間[left, right]。
回傳大小與queries相同之整數陣列answer,其中answer[i]代表arr在區間queries[i]所有元素異或(exclusive or)的值。

方向

先複習異或(exclusive or)的真值表

A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

異或有個重要的性質: 對合(involution),也就是其逆函數等同於自身。
A XOR B XOR B = A XOR 0 = A
白話點就是,自己異或自己,就會把自己消除
https://ithelp.ithome.com.tw/upload/images/20240913/20168787nxYxoPFPmZ.jpg

這題最naive的作法,就是區間每個元素一個個來異或,時間複雜度為O(N^2)。

而異或有著對合的性質,我們可以利用此特性,將這題轉化為類似前綴和(prefix)的題目。
先建立一個前綴異或陣列prefix_xorprefix_xor[i]代表arr從索引零到i的異或值。
對於題目每個要求的區間[left, right],只需用prefix_xor[right] XOR prefix_xor[left - 1]即可求得。
XOR prefix_xor[left - 1]的作用就是把索引零到left之前的異或值都消除掉。

實作

class Solution
{
public:
    vector<int> xorQueries(vector<int>& arr, const vector<vector<int>>& queries)
    {
        size_t arr_size = arr.size();
        for (size_t i = 1; i < arr_size; i++)
            arr[i] ^= arr[i - 1];

        size_t n = queries.size();
        vector<int> res(n, 0);
        for (size_t i = 0; i < n; i++)
            res[i] = arr[queries[i][1]]
                     ^ (queries[i][0] == 0 ? 0 : arr[queries[i][0] - 1]);
        return res;
    }
};

分析

arr長度為N,quireis長度為M
時間複雜度: O(N + M) = O(max(M, N)),建立前綴異或O(N),建立answerO(M * 1)。
空間複雜度: O(1),這題直接把前綴存回arr中,因此無須額外空間。

結果

Time Submitted Status Runtime Memory Language
09/13/2024 19:01 Accepted 68 ms 41.3 MB cpp

上一篇
[9/12] 數有幾個合法的字串
下一篇
[9/14] 連續最大值的長度
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言